package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/first-missing-positive/">缺失的第一个正数(First Missing Positive)</a>
 * <p>给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。</p>
 * <p>请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：nums = [1,2,0]
 *      输出：3
 *      解释：范围 [1,2] 中的数字都在数组中。
 *
 * 示例 2：
 *      输入：nums = [3,4,-1,1]
 *      输出：2
 *      解释：1 在数组中，但 2 没有。
 *
 * 示例 3：
 *      输入：nums = [7,8,9,11,12]
 *      输出：1
 *      解释：最小的正数 1 没有出现。
 * </pre>
 * </p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 10^5</li>
 *     <li>-2^31 <= nums[i] <= 2^31 - 1</li>
 * </ul>
 *
 * @author c2b
 * @since 2024/8/20 16:00
 */
public class LC0041FirstMissingPositive_H {

    static class Solution {
        /**
         * 使用置换的方法，将给定的数组「恢复」成下面的形式：如果数组中包含 x∈[1,N]，那么恢复后，数组的第 x−1 个元素为 x。
         * <p>在恢复后，数组应当有 [1, 2, ..., N] 的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。</p>
         * <p>以题目中的示例二 [3, 4, -1, 1] 为例，恢复后的数组应当为 [1, -1, 3, 4]，我们就可以知道缺失的数为 2。</p>
         * <p>那么我们如何将数组进行恢复呢？</p>
         * <p>
         * 我们可以对数组进行一次遍历，对于遍历到的数 x=nums[i]，如果 x∈[1,N]，我们就知道 x 应当出现在数组中的 x−1 的位置，因此交换 nums[i] 和 nums[x−1]，这样 x 就出现在了正确的位置。
         * 在完成交换后，新的 nums[i] 可能还在 [1,N] 的范围内，我们需要继续进行交换操作，直到 x不属于[1,N]。
         * </p>
         * 注意到上面的方法可能会陷入死循环。如果 nums[i] 恰好与 nums[x−1] 相等，那么就会无限交换下去。此时我们有 nums[i]=x=nums[x−1]，说明 x 已经出现在了正确的位置。因此我们可以跳出循环，开始遍历下一个数。
         * <p>
         * 由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为 N，整个方法的时间复杂度为 O(N)。
         */
        public int firstMissingPositive(int[] nums) {
            int len = nums.length;
            for (int i = 0; i < nums.length; i++) {
                // val > 0 && val <= len && 使 下标 val-1 位置的值等于 val。
                // 例如：nums[0]=3，nums[2]=5。让值3换到下标2对应的位置上
                while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                    int temp = nums[i];
                    nums[i] = nums[nums[i] - 1];
                    nums[nums[i] - 1] = temp;

                }
            }
            for (int i = 0; i < len; i++) {
                if (nums[i] != i + 1) {
                    return i + 1;
                }
            }
            return len + 1;
        }
    }
}
